Recently, as the information society has been advanced, the amount of data processed by individuals, business, and the like has been increased, and thus, costs required for efficiently managing such data have also been considerably increased. However, it is not in reason to impose costs required for such information management on every member of the information society, and thus, cases of storing information by utilizing an external database service has been gradually increased. However, the utilization of an external database has an arising problem that an external database is not reliable as can be seen from a case of a data spill or the like which is frequently generated recently, so a proposal of a solution thereto has emerged as a very critical issue.
Various methods have been proposed as solutions, and among them, a method highlighted as the most perfect solution is encrypting all the data stored in a database. An encryption system theoretically guarantees secrecy of encrypted data, thus securing secrecy of all the stored data. That is, it means that, although an external attacker or a database manager obtains stored encrypted data, it cannot obtain actually meaningful information.
This encryption of data is a method that perfectly guarantees confidentialness of stored information, but has shortcomings that various services provided by a database server cannot be provided. In other words, if information is encrypted by using a general encryption technique, searching, calculation, and the like cannot be performed on data stored in the database, and thus, in order to perform a particular operation on data, a user should receive all the data stored in a server and perform decrypting thereon by himself before performing the operation.
Meanwhile, a searchable encryption technique is an encryption technique devised to search for data including a particular keyword while guaranteeing confidentialness of the data. Since various functions provided in a database are based on searching for information including particular keywords, a searchable encryption system is considered to be the most potential solution to the foregoing problems.
Research into a searchable encryption system was formalized in the early 2000s, and currently, a searchable encryption system includes four steps such as ‘key setting step’, ‘encryption and index generation step’, ‘trap door generation step’, and ‘searching step’. Each step will be described in detail as follows. In the key setting step, a user sets every variable required for the system and prepares an encryption/decryption key and a secret key to be used for searching. In the encryption and index generation step, the user encrypts given data by using the encryption key and the given data, and generates an index to be used for searching later. Here, encrypted data and index are stored in an external database. In the trap door generation step, the user generates a trap door to be used for searching for data by using the secret key of the user and a keyword desired to be searched, and here, it is designed such that a server cannot obtain information regarding the keyword desired to be searched from the trap door. Finally, in the searching step, the server searches for data desired by the user by using the given trap door and stored index. In the searching step, the server is designed to recognize only whether or not the stored data is the user desired data and to be prevented from recognizing any information regarding the user searched keyword or content of the stored data.
As for the searchable encryption system, a searchable encryption system based on a symmetric key was first researched. The symmetric key-based searchable encryption system uses the same secret key for index generation and searching, and therefore, only a user owning a secret key performs an encryption and index generation step. That is, the symmetric key-based searchable encryption system may be considered to be a technique for allowing a single user to effectively manage data owned by the user through an external database. Thereafter, a public key-based searchable encryption system in which a public key for performing an index generation step is different from a secret key used for searching was researched. Since the public key-based searchable encryption system allows a certain data provider to generate an index and ciphertexts by using a public key, it can be used in various applications in comparison to the symmetric key-based searchable encryption system.
A future computing environment is changing to a cloud computing environment in which all the operations are processed by cloud servers. The biggest issue in the cloud computing is to guarantee confidentiality of data concentrated on the cloud server, which essentially requires an application of a searchable encryption system.
However, it is difficult to effectively protect data utilized in a multi-user computing environment represented by cloud computing only with the existing symmetric key or public key-based searchable encryption systems. A searchable encryption system for a multi-user environment requires a method for allowing multiple users to freely encrypt and provide their own data and freely search for data encrypted by different users. In the multi-user searchable encryption system, since multiple users may freely provide and search for data, various requirements, other than requirements of a general symmetric key-public searchable encryption system, exist. When multiple users share data through a database, the most critical issue is to authenticate data stored in the database. In other words, if inappropriate data is found, a user providing such data can be traced. In addition, in order to clarify where the responsibility for inappropriate data lies, a process of verifying every index is required in the course of storing data in a server. However, the multi-user searchable encryption system developed to date does not take such a data verification and tracing function into consideration.